

In [ ]:

    
%%HTML
<style>
.container { width:100% }
</style>

Bidirectional A$^*$ Search



In [ ]:

    
import Set

The function search takes three arguments to solve a search problem:

start is the start state of the search problem,
goalis the goal state, and
next_states is a function with signature $\texttt{next_states}:Q \rightarrow 2^Q$, where $Q$ is the set of states. For every state $s \in Q$, $\texttt{next_states}(s)$ is the set of states that can be reached from $s$ in one step.
heuristic is a function that takes two states as arguments. It returns an estimate of the length of the shortest path between these states. If successful, search returns a path from start to goal that is a solution of the search problem $$ \langle Q, \texttt{next_states}, \texttt{start}, \texttt{goal} \rangle. $$

The function search implements bidirectional A$^*$ search.



In [ ]:

    
def search(start, goal, next_states, heuristic):
    estimate  = heuristic(start, goal)
    ParentA   = { start: start }
    ParentB   = { goal : goal  }
    DistanceA = { start: 0 }
    DistanceB = { goal : 0 }
    EstimateA = { start: estimate }
    EstimateB = { goal : estimate }
    FrontierA = Set.Set()   
    FrontierB = Set.Set()
    FrontierA.insert( (estimate, start) )
    FrontierB.insert( (estimate, goal ) )
    while not FrontierA.isEmpty() and not FrontierB.isEmpty():
        guessA, stateA = FrontierA.pop()
        guessB, stateB = FrontierB.pop()
        stateADist = DistanceA[stateA]
        stateBDist = DistanceB[stateB]
        if guessA <= guessB:
            FrontierB.insert( (guessB, stateB) )
            for ns in next_states(stateA):
                oldEstimate = EstimateA.get(ns, None)
                newEstimate = stateADist + 1 + heuristic(ns, goal)
                if oldEstimate == None or newEstimate < oldEstimate:
                    ParentA  [ns] = stateA
                    DistanceA[ns] = stateADist + 1
                    EstimateA[ns] = newEstimate
                    FrontierA.insert( (newEstimate, ns) )
                    if oldEstimate != None:
                        FrontierA.delete( (oldEstimate, ns) )
                if DistanceB.get(ns, None) != None:
                    stateNum = len(DistanceA) + len(DistanceB)
                    print('number of states:', stateNum)
                    return combinePaths(ns, ParentA, ParentB)
        else:
            FrontierA.insert( (guessA, stateA) )
            for ns in next_states(stateB):
                oldEstimate = EstimateB.get(ns, None)
                newEstimate = stateBDist + 1 + heuristic(start, ns)
                if oldEstimate == None or newEstimate < oldEstimate:
                    ParentB  [ns] = stateB
                    DistanceB[ns] = stateBDist + 1
                    EstimateB[ns] = newEstimate
                    FrontierB.insert( (newEstimate, ns) )
                    if oldEstimate != None:
                        FrontierB.delete( (oldEstimate, ns) )
                if DistanceA.get(ns, None) != None:
                    stateNum = len(DistanceA) + len(DistanceB)
                    print('number of states:', stateNum)
                    return combinePaths(ns, ParentA, ParentB)

Given a state and a parent dictionary Parent, the function path_to returns a path leading to the given state.



In [ ]:

    
def path_to(state, Parent):
    p = Parent[state]
    if p == state:
        return [state]
    return path_to(p, Parent) + [state]

The function combinePath takes three parameters:

state is a state that has been reached in bidirectional BFS from both start and goal.
ParentA is the parent dictionary that has been build when searching from start. If $\texttt{ParentA}[s_1] = s_2$ holds, then either $s_1 = s2 = \texttt{start}$ or $s_1 \in \texttt{next_states}(s_2)$.
ParentB is the parent dictionary that has been build when searching from goal. If $\texttt{ParentB}[s_1] = s_2$ holds, then either $s_1 = s2 = \texttt{goal}$ or $s_1 \in \texttt{next_states}(s_2)$. The function returns a path from startto goal.



In [ ]:

    
def combinePaths(state, ParentA, ParentB):
        Path1 = path_to(state, ParentA)
        Path2 = path_to(state, ParentB)
        return Path1[:-1] + Path2[::-1] # Path2 is reversed

Lets draw the start state and animate the solution that has been found.



In [ ]:

    
%run Sliding-Puzzle.ipynb



In [ ]:

    
%%time
Path = search(start, goal, next_states, manhattan)
print(len(Path)-1)



In [ ]:

    
animation(Path)

Let's try the real thing.



In [ ]:

    
%%time
Path = search(start2, goal2, next_states, manhattan)
print(len(Path)-1)



In [ ]:

    
animation(Path)



In [ ]: